package com.example.javamaday.queue;

public class IndexMinPriorityQueue<T extends Comparable<T>> {

    private T[] items;
    private int[] pq;  // 保存每个元素在items数组中的索引，pq数组需要堆有序
    private int[] qp;  // 保存pq的逆序，pq的值作为索引，pq的索引作为值

    private int N; //记录元素个数

    // 构造方法
    public IndexMinPriorityQueue(int capacity) {
        this.items = (T[]) new Comparable[capacity + 1];
        this.pq = new int[capacity + 1];
        this.qp = new int[capacity + 1];
        this.N = 0;
        // 默认情况下，队列中没有存储任何数据, 让qp中的元素的都为-1
        for (int i = 0; i < qp.length; i++) {
            qp[i] = -1;
        }
    }

    public int getSize() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    private boolean less(int i, int j) {
        return items[pq[i]].compareTo(items[pq[j]]) < 0;
    }

    private void exch(int i, int j) {
        // 交换pq中的数据
        int tmp = pq[i];
        pq[i] = pq[j];
        pq[j] = tmp;
        // 更新qp中的数据
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }

    public boolean contains(int k) {
        return qp[k] != -1;
    }

    public int getMinIndex() {
        return pq[1];
    }

    private void insert(int i, T t) {
        if (contains(i)) {
            return;
        }
        N++;
        items[i] = t;
        pq[N] = i;
        qp[i] = N;
        // 对上浮完成堆的调整
        swim(N);
    }

    public int delMin() {
        // 获取最小元素关联的索引
        int minIndex = pq[1];
        // 交换pq中索引1处和最大索引处的元素
        exch(1, N);
        //删除qp中对应的内容
        qp[pq[N]] = -1;
        // 删除pq中对应的内容
        pq[N] = -1;
        // 删除items中对应的内容
        System.out.println("要删除的值 = " + items[minIndex]);
        items[minIndex] = null;
        // 元素个数 -1
        N--;
        // 元素下沉调整
        sink(1);
        return minIndex;
    }

    public void delete(int i) {
        // 找到i在pq中的索引
        int k = qp[i];
        // 交换pq中k处的值和索引N处的值
        exch(k, N);
        // 删除qp中的内容
        qp[pq[N]] = -1;
        // 删除pq值的内容
        pq[N] = -1;
        // 删除items中的内容
        items[k] = null;
        // 元素的数量-1
        N--;
        // 堆调整
        sink(k);
        swim(k);
    }

    // 修改索引i关联的元素为t
    public void changeItem(int i, T t) {
        items[i] = t;
        int k = qp[i];
        sink(k);
        swim(k);
    }

    // 上浮算法，使索引k处的元素处于正确的位置
    public void swim(int k) {
        while (k > 1) {
            if (less(k, k / 2)) {
                exch(k, k / 2);
            }
            k = k / 2;
        }
    }

    // 下沉算法，使索引k处的元素处于正确的位置
    public void sink(int k) {
        while (2 * k <= N) {
            int min;
            // 如果有右子节点
            if (2 * k + 1 <= N) {
                if (less(k * 2, k * 2 + 1)) {
                    min = 2 * k;
                } else {
                    min = 2 * k + 1;
                }
            } else {
                min = 2 * k;
            }
            if (less(k, min)) {
                break;
            }
            exch(k, min);
            k = min;
        }
    }

    public static void main(String[] args) {
        IndexMinPriorityQueue<String> queue = new IndexMinPriorityQueue<String>(10);
        queue.insert(0, "A");
        queue.insert(1, "C");
        queue.insert(2, "F");

        queue.changeItem(1, "G");

        while (!queue.isEmpty()) {
            queue.delMin();
        }
    }
}

